#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 695. 岛屿的最大面积.py
@time: 2022/3/2 16:42
@desc: https://leetcode-cn.com/problems/max-area-of-island/
> 给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

1. dp
2. Ot(mn), Os(mn)

'''
class Solution:
    def maxAreaOfIsland(self, grid: list) -> int:
        def dfs(grid, x, y):
            if not 0<=x<m or not 0<=y<n or x==m or y==n or not grid[x][y]==1: return 0
            grid[x][y] = 0
            ans = 1
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ans += dfs(grid, x+dx, y+dy)
            return ans
        ans = 0
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                ans = max(dfs(grid, i, j), ans)
        return ans